package longestPalindrome

func longestPalindrome(s string) string {
	//回文串分奇数和偶数长度两种情况
	begin, end := 0, 0
	l := len(s)
	//从回文串中心向外搜索
	for i := 0; i < l; i += 1 {
		//从i 为中心奇数最大长度回文串
		left_1, right_1 := expend(s, i, i, l)
		//从i 为中心长度为偶数最大长度的回文串
		left_2, right_2 := expend(s, i, i+1, l)
		curr_max := end - begin
		if (right_1 - left_1) > curr_max {
			begin, end = left_1, right_1
		}
		if (right_2 - left_2) > curr_max {
			begin, end = left_2, right_2
		}
	}
	return s[begin : end+1]
}

func expend(s string, left int, right int, sLen int) (maxLeft int, maxRight int) {
	for left >= 0 && right < sLen && s[left] == s[right] {
		left -= 1
		right += 1
	}
	//因为结束时下标均会超出实际长度长度1
	return left + 1, right - 1
}
